#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *给定一个正整数n，将其拆分为 k 个 正整数 的和（k >= 2），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积。



示例 1:

输入: n =
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 ×3 ×4 = 36。
//
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/integer-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 2   1 1
 3   1 2
 4   2 2
 5   2 3
 6   2 2 2
 7   2 2 3
 8   2 2 4


//TODO 这个题抄的
 * */
// 1 dp[i] dp[i] 代表最大值 i代表 1 - n
// 2 递归式子 循环j    j*(i-j) 分成两个的 和 dp[i-j]*j (分成多份最大 每次都在一直更新dp[i]的值)
// 3 遍历的话从双层循环 i是一个外层大的要求最终结果的 j是从1开始试探求 dp[i]最大的
// 4 初始化值 dp[0]=0 dp[1]=1 dp[2]=2 感觉实际意义不大
int integerBreak(int n) {

    vector<int> dp(n + 1, 0);

    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 1;
    for (int i = 3; i <= n; ++i) {

        for (int j = 1; j < i; ++j) {
            int max1 = j * (i - j);
            //int max2=dp[i-j]*j; 这俩种都行的并不是非要写成他这样
            int max2 = dp[j] * (i - j);
            int max3 = max(max1, max2);
            if (max3 > dp[i]) {
                dp[i] = max3;//一直在更新dp
            }
        }

    }

    return dp[n];
}
